package leetcode.year2021.month10;

import java.util.LinkedList;
import java.util.List;

public class _10_01RemoveNthFromEnd19 {
  /**
   * 三种解法
   * 1. 快慢指针
   * 2.栈
   * 3.遍历两次
   * @param head
   * @param n
   * @return
   */
  public ListNode removeNthFromEnd(ListNode head, int n) {
    LinkedList<ListNode> stack = new LinkedList<>();

    ListNode dummy = new ListNode(0,head);

    ListNode currNode = dummy;

    while (currNode != null){
      stack.push(currNode);
      currNode = currNode.next;
    }

    for (int i = 0; i < n; i++) {
      stack.pop();
    }

    ListNode pop = stack.peek();
    pop.next = pop.next.next;

    return dummy.next;
  }


  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }


  /**
   * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
   *
   * 进阶：你能尝试使用一趟扫描实现吗？
   *
   * 输入：head = [1,2,3,4,5], n = 2
   * 输出：[1,2,3,5]
   * 示例 2：
   *
   * 输入：head = [1], n = 1
   * 输出：[]
   * 示例 3：
   *
   * 输入：head = [1,2], n = 1
   * 输出：[1]
   *
   * 来源：力扣（LeetCode）
   * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
   * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
   */

}
